Zero-Error Capacity of $P$-ary Shift Channels and FIFO Queues

摘要

The objects of study of this paper are communication channels in which thedominant type of noise are symbol shifts, the main motivating examples beingtiming and bit-shift channels. Two channel models are introduced and theirzero-error capacities and zero-error-detection capacities determined byexplicit constructions of optimal codes. Model A can be informally described asfollows: 1) The information is stored in an $ n $-cell register, where eachcell is either empty or contains a particle of one of $ P $ possible types, and2) due to the imperfections of the device each of the particles may be shiftedseveral cells away from its original position over time. Model B is anabstraction of a single-server queue: 1) The transmitter sends packets from a $P $-ary alphabet through a queuing system with an infinite buffer and aFirst-In-First-Out (FIFO) service procedure, and 2) each packet is beingprocessed by the server for a random number of time slots. More general modelsincluding additional types of noise that the particles/packets can experienceare also studied, as are the continuous-time versions of these problems.